<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="Content-Type" content="text/xhtml;charset=UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=9"/>
<meta name="generator" content="Doxygen 1.8.10"/>
<title>Introduction_to_Algorithms: IntroductionToAlgorithm::TreeAlgorithm Namespace Reference</title>
<link href="tabs.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="jquery.js"></script>
<script type="text/javascript" src="dynsections.js"></script>
<link href="navtree.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="resize.js"></script>
<script type="text/javascript" src="navtreedata.js"></script>
<script type="text/javascript" src="navtree.js"></script>
<script type="text/javascript">
  $(document).ready(initResizable);
  $(window).load(resizeHeight);
</script>
<link href="search/search.css" rel="stylesheet" type="text/css"/>
<script type="text/javascript" src="search/searchdata.js"></script>
<script type="text/javascript" src="search/search.js"></script>
<script type="text/javascript">
  $(document).ready(function() { init_search(); });
</script>
<link href="doxygen.css" rel="stylesheet" type="text/css" />
</head>
<body>
<div id="top"><!-- do not remove this div, it is closed by doxygen! -->
<div id="titlearea">
<table cellspacing="0" cellpadding="0">
 <tbody>
 <tr style="height: 56px;">
  <td id="projectalign" style="padding-left: 0.5em;">
   <div id="projectname">Introduction_to_Algorithms
   </div>
  </td>
 </tr>
 </tbody>
</table>
</div>
<!-- end header part -->
<!-- Generated by Doxygen 1.8.10 -->
<script type="text/javascript">
var searchBox = new SearchBox("searchBox", "search",false,'Search');
</script>
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="namespaces.html"><span>Namespaces</span></a></li>
      <li><a href="annotated.html"><span>Classes</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
      <li>
        <div id="MSearchBox" class="MSearchBoxInactive">
        <span class="left">
          <img id="MSearchSelect" src="search/mag_sel.png"
               onmouseover="return searchBox.OnSearchSelectShow()"
               onmouseout="return searchBox.OnSearchSelectHide()"
               alt=""/>
          <input type="text" id="MSearchField" value="Search" accesskey="S"
               onfocus="searchBox.OnSearchFieldFocus(true)" 
               onblur="searchBox.OnSearchFieldFocus(false)" 
               onkeyup="searchBox.OnSearchFieldChange(event)"/>
          </span><span class="right">
            <a id="MSearchClose" href="javascript:searchBox.CloseResultsWindow()"><img id="MSearchCloseImg" border="0" src="search/close.png" alt=""/></a>
          </span>
        </div>
      </li>
    </ul>
  </div>
  <div id="navrow2" class="tabs2">
    <ul class="tablist">
      <li><a href="namespaces.html"><span>Namespace&#160;List</span></a></li>
      <li><a href="namespacemembers.html"><span>Namespace&#160;Members</span></a></li>
    </ul>
  </div>
</div><!-- top -->
<div id="side-nav" class="ui-resizable side-nav-resizable">
  <div id="nav-tree">
    <div id="nav-tree-contents">
      <div id="nav-sync" class="sync"></div>
    </div>
  </div>
  <div id="splitbar" style="-moz-user-select:none;" 
       class="ui-resizable-handle">
  </div>
</div>
<script type="text/javascript">
$(document).ready(function(){initNavTree('namespace_introduction_to_algorithm_1_1_tree_algorithm.html','');});
</script>
<div id="doc-content">
<!-- window showing the filter options -->
<div id="MSearchSelectWindow"
     onmouseover="return searchBox.OnSearchSelectShow()"
     onmouseout="return searchBox.OnSearchSelectHide()"
     onkeydown="return searchBox.OnSearchSelectKey(event)">
</div>

<!-- iframe showing the search results (closed by default) -->
<div id="MSearchResultsWindow">
<iframe src="javascript:void(0)" frameborder="0" 
        name="MSearchResults" id="MSearchResults">
</iframe>
</div>

<div class="header">
  <div class="summary">
<a href="#nested-classes">Classes</a> &#124;
<a href="#func-members">Functions</a>  </div>
  <div class="headertitle">
<div class="title">IntroductionToAlgorithm::TreeAlgorithm Namespace Reference</div>  </div>
</div><!--header-->
<div class="contents">

<p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html" title="Namespace of TreeAlgorithm. ">TreeAlgorithm</a>.  
<a href="#details">More...</a></p>
<table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="nested-classes"></a>
Classes</h2></td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_tree_algorithm_1_1_binary_tree.html">BinaryTree</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">BinaryTree：二叉树，算法导论10章10.4节  <a href="struct_introduction_to_algorithm_1_1_tree_algorithm_1_1_binary_tree.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">struct &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="struct_introduction_to_algorithm_1_1_tree_algorithm_1_1_binary_tree_node.html">BinaryTreeNode</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">BinaryTreeNode：二叉树的节点，算法导论xx章xx节  <a href="struct_introduction_to_algorithm_1_1_tree_algorithm_1_1_binary_tree_node.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:"><td class="memItemLeft" align="right" valign="top">class &#160;</td><td class="memItemRight" valign="bottom"><a class="el" href="class_introduction_to_algorithm_1_1_tree_algorithm_1_1_search_tree.html">SearchTree</a></td></tr>
<tr class="memdesc:"><td class="mdescLeft">&#160;</td><td class="mdescRight">SearchTree：二叉搜索树，算法导论12章  <a href="class_introduction_to_algorithm_1_1_tree_algorithm_1_1_search_tree.html#details">More...</a><br /></td></tr>
<tr class="separator:"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table><table class="memberdecls">
<tr class="heading"><td colspan="2"><h2 class="groupheader"><a name="func-members"></a>
Functions</h2></td></tr>
<tr class="memitem:abd9431ca8d1a40f70b6c72c732fc5892"><td class="memTemplParams" colspan="2">template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </td></tr>
<tr class="memitem:abd9431ca8d1a40f70b6c72c732fc5892"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#abd9431ca8d1a40f70b6c72c732fc5892">inorder_walk</a> (std::shared_ptr&lt; NodeType &gt; root, ActionType action=[](typename NodeType::T){})</td></tr>
<tr class="memdesc:abd9431ca8d1a40f70b6c72c732fc5892"><td class="mdescLeft">&#160;</td><td class="mdescRight">inorder_walk：二叉树的中序遍历  <a href="#abd9431ca8d1a40f70b6c72c732fc5892">More...</a><br /></td></tr>
<tr class="separator:abd9431ca8d1a40f70b6c72c732fc5892"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a3d57267cd5fea456f6e001dc22d07c85"><td class="memTemplParams" colspan="2">template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </td></tr>
<tr class="memitem:a3d57267cd5fea456f6e001dc22d07c85"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#a3d57267cd5fea456f6e001dc22d07c85">preorder_walk</a> (std::shared_ptr&lt; NodeType &gt; root, ActionType action=[](typename NodeType::T){})</td></tr>
<tr class="memdesc:a3d57267cd5fea456f6e001dc22d07c85"><td class="mdescLeft">&#160;</td><td class="mdescRight">preorder_walk：二叉树的前序遍历  <a href="#a3d57267cd5fea456f6e001dc22d07c85">More...</a><br /></td></tr>
<tr class="separator:a3d57267cd5fea456f6e001dc22d07c85"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a49b5467191bd51c25ad7e7bfbed51339"><td class="memTemplParams" colspan="2">template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </td></tr>
<tr class="memitem:a49b5467191bd51c25ad7e7bfbed51339"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#a49b5467191bd51c25ad7e7bfbed51339">postorder_walk</a> (std::shared_ptr&lt; NodeType &gt; root, ActionType action=[](typename NodeType::T){})</td></tr>
<tr class="memdesc:a49b5467191bd51c25ad7e7bfbed51339"><td class="mdescLeft">&#160;</td><td class="mdescRight">postorder_walk：二叉树的后序遍历  <a href="#a49b5467191bd51c25ad7e7bfbed51339">More...</a><br /></td></tr>
<tr class="separator:a49b5467191bd51c25ad7e7bfbed51339"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a96be2938a006ec461c1b0a59d6bee3b5"><td class="memTemplParams" colspan="2">template&lt;typename NodeType &gt; </td></tr>
<tr class="memitem:a96be2938a006ec461c1b0a59d6bee3b5"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#a96be2938a006ec461c1b0a59d6bee3b5">left_rotate</a> (std::shared_ptr&lt; NodeType &gt; node, std::shared_ptr&lt; NodeType &gt; &amp;root)</td></tr>
<tr class="memdesc:a96be2938a006ec461c1b0a59d6bee3b5"><td class="mdescLeft">&#160;</td><td class="mdescRight">left_rotate：二叉树的左旋转操作  <a href="#a96be2938a006ec461c1b0a59d6bee3b5">More...</a><br /></td></tr>
<tr class="separator:a96be2938a006ec461c1b0a59d6bee3b5"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:adeb83a10f8daa65c5cf5921737a04da0"><td class="memTemplParams" colspan="2">template&lt;typename NodeType &gt; </td></tr>
<tr class="memitem:adeb83a10f8daa65c5cf5921737a04da0"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#adeb83a10f8daa65c5cf5921737a04da0">right_rotate</a> (std::shared_ptr&lt; NodeType &gt; node, std::shared_ptr&lt; NodeType &gt; &amp;root)</td></tr>
<tr class="memdesc:adeb83a10f8daa65c5cf5921737a04da0"><td class="mdescLeft">&#160;</td><td class="mdescRight">right_rotate：二叉树的右旋转操作  <a href="#adeb83a10f8daa65c5cf5921737a04da0">More...</a><br /></td></tr>
<tr class="separator:adeb83a10f8daa65c5cf5921737a04da0"><td class="memSeparator" colspan="2">&#160;</td></tr>
<tr class="memitem:a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5"><td class="memTemplParams" colspan="2">template&lt;typename NodeType &gt; </td></tr>
<tr class="memitem:a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5"><td class="memTemplItemLeft" align="right" valign="top">void&#160;</td><td class="memTemplItemRight" valign="bottom"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html#a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5">transplant</a> (std::shared_ptr&lt; NodeType &gt; node_src, std::shared_ptr&lt; NodeType &gt;node_dst, std::shared_ptr&lt; NodeType &gt; &amp;root)</td></tr>
<tr class="memdesc:a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5"><td class="mdescLeft">&#160;</td><td class="mdescRight">transplant：二叉树的剪切操作  <a href="#a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5">More...</a><br /></td></tr>
<tr class="separator:a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5"><td class="memSeparator" colspan="2">&#160;</td></tr>
</table>
<a name="details" id="details"></a><h2 class="groupheader">Detailed Description</h2>
<div class="textblock"><p>Namespace of <a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html" title="Namespace of TreeAlgorithm. ">TreeAlgorithm</a>. </p>
<p>该命名空间内包含所有树算法 </p>
</div><h2 class="groupheader">Function Documentation</h2>
<a class="anchor" id="abd9431ca8d1a40f70b6c72c732fc5892"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::inorder_walk </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>root</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>action</em> = <code>[](typename&#160;NodeType::T){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>inorder_walk：二叉树的中序遍历 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">root</td><td>二叉树的根节点，强引用 </td></tr>
    <tr><td class="paramname">func</td><td>对二叉树节点的操作 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行对二叉树的中序遍历，遍历时执行指定操作 算法：</p><ul>
<li>对左子节点前序遍历</li>
<li>对本节点执行操作</li>
<li>对右子节点前序遍历</li>
</ul>
<p>时间复杂度O(n)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00077">77</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
<a class="anchor" id="a96be2938a006ec461c1b0a59d6bee3b5"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::left_rotate </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>node</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt; &amp;&#160;</td>
          <td class="paramname"><em>root</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>left_rotate：二叉树的左旋转操作 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">node</td><td>待旋转的节点，强引用 </td></tr>
    <tr><td class="paramname">root：</td><td>二叉树的根节点的强引用（当node指向树根时，旋转会导致丢失树根信息，此时由root返回新的树根） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行二叉树进行左旋转。设node为被旋转的点，l_node为它的左子节点，r_node为它的右子节点。 则旋转的效果是：r_node取代了node的位置；而node现在挂靠在r_node的左子；r_node原来的左子现在成为node的右子</p>
<p><code></p><pre>
        |                                                |
       node                                            r_node
      /    \                                           /    \
  l_node  r_node        -- 左旋  --&gt;                  node  r_r_node
         /    \                                     /    \
    l_r_node r_r_node                           l_node  l_r_node
</pre><p></code></p>
<p>时间复杂度O(1)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00157">157</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
<a class="anchor" id="a49b5467191bd51c25ad7e7bfbed51339"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::postorder_walk </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>root</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>action</em> = <code>[](typename&#160;NodeType::T){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>postorder_walk：二叉树的后序遍历 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">root</td><td>二叉树的根节点，强引用 </td></tr>
    <tr><td class="paramname">func</td><td>对二叉树节点的操作 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行对二叉树的后序遍历，遍历时执行指定操作。 算法：</p>
<ul>
<li>对左子节点后续遍历</li>
<li>对右子节点后续遍历</li>
<li>对本节点执行操作</li>
</ul>
<p>时间复杂度O(n)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00127">127</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
<a class="anchor" id="a3d57267cd5fea456f6e001dc22d07c85"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType , typename ActionType  = std::function&lt;void (typename NodeType::T)&gt;&gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::preorder_walk </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>root</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">ActionType&#160;</td>
          <td class="paramname"><em>action</em> = <code>[](typename&#160;NodeType::T){}</code>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>preorder_walk：二叉树的前序遍历 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">root</td><td>二叉树的根节点，强引用 </td></tr>
    <tr><td class="paramname">func</td><td>对二叉树节点的操作 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行对二叉树的前序遍历，遍历时执行指定操作 算法：</p><ul>
<li>对本节点执行操作</li>
<li>对左子节点前序遍历</li>
<li>对右子节点前序遍历</li>
</ul>
<p>时间复杂度O(n)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00101">101</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
<a class="anchor" id="adeb83a10f8daa65c5cf5921737a04da0"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::right_rotate </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>node</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt; &amp;&#160;</td>
          <td class="paramname"><em>root</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>right_rotate：二叉树的右旋转操作 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">node</td><td>待旋转的节点，强引用 </td></tr>
    <tr><td class="paramname">root：</td><td>二叉树的根节点的强引用（当node指向树根时，旋转会导致丢失树根信息，此时由root返回新的树根） </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行二叉树进行右旋转。设node为被旋转的点，l_node为它的左子节点，r_node为它的右子节点。 则旋转的效果是：l_node取代了node的位置；而node现在挂靠在r_node的右子；l_node原来的右子现在成为node的左子</p>
<p><code></p><pre>
                  |                                                |
                 node                                            l_node
                /    \                                           /    \
             l_node  r_node        -- 右旋  --&gt;              l_l_node  node
            /    \                                                    /    \
       l_l_node r_l_node                                         r_l_node  r_node
</pre><p></code> 时间复杂度O(1)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00204">204</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
<a class="anchor" id="a4fb6d9c7d8b75a8d6ec4ee79fc0b1de5"></a>
<div class="memitem">
<div class="memproto">
<div class="memtemplate">
template&lt;typename NodeType &gt; </div>
      <table class="memname">
        <tr>
          <td class="memname">void IntroductionToAlgorithm::TreeAlgorithm::transplant </td>
          <td>(</td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>node_src</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt;&#160;</td>
          <td class="paramname"><em>node_dst</em>, </td>
        </tr>
        <tr>
          <td class="paramkey"></td>
          <td></td>
          <td class="paramtype">std::shared_ptr&lt; NodeType &gt; &amp;&#160;</td>
          <td class="paramname"><em>root</em>&#160;</td>
        </tr>
        <tr>
          <td></td>
          <td>)</td>
          <td></td><td></td>
        </tr>
      </table>
</div><div class="memdoc">

<p>transplant：二叉树的剪切操作 </p>
<dl class="params"><dt>Parameters</dt><dd>
  <table class="params">
    <tr><td class="paramname">node_src</td><td>剪切源节点 </td></tr>
    <tr><td class="paramname">root：</td><td>二叉树的根节点的强引用（当node指向树根时，剪切导致丢失树根信息，此时由root返回新的树根） </td></tr>
    <tr><td class="paramname">node_dst</td><td>剪切目的节点 </td></tr>
  </table>
  </dd>
</dl>
<dl class="section return"><dt>Returns</dt><dd>void</dd></dl>
<p>本函数执行二叉树的剪切操作。剪切操作要求目的节点是非空节点（若是空节点则抛出异常）。本操作将node_src剪切到node_dst中。下图中，两个节点之间有两个链接：一个是父&ndash;&gt;子，另一个是子&ndash;&gt;父 剪切操作可能会仅仅剪断一个连接</p>
<p><code></p><pre>
                src_p         dst_p                                    src_p         dst_p             dst_p
                  ||            ||                               (父--&gt;子)|             ||                |(子---&gt;父)
                node_src     node_dst         ---剪切 --&gt;               node_src      node_src        node_dst
                //   \      //    \                                 //     \      //     \        //     \
</pre><p></code> 时间复杂度O(1)，空间复杂度O(1) </p>

<p>Definition at line <a class="el" href="binarytree_8h_source.html#l00249">249</a> of file <a class="el" href="binarytree_8h_source.html">binarytree.h</a>.</p>

</div>
</div>
</div><!-- contents -->
</div><!-- doc-content -->
<!-- start footer part -->
<div id="nav-path" class="navpath"><!-- id is needed for treeview function! -->
  <ul>
    <li class="navelem"><a class="el" href="namespace_introduction_to_algorithm.html">IntroductionToAlgorithm</a></li><li class="navelem"><a class="el" href="namespace_introduction_to_algorithm_1_1_tree_algorithm.html">TreeAlgorithm</a></li>
    <li class="footer">Generated by
    <a href="http://www.doxygen.org/index.html">
    <img class="footer" src="doxygen.png" alt="doxygen"/></a> 1.8.10 </li>
  </ul>
</div>
</body>
</html>
